package com.ljc;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author clj
 * @date 2022/12/15
 * @desc
 * Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
 * You must implement a solution with a linear runtime complexity and use only constant extra space.
 *
 * Example 1:
 * Input: nums = [2,2,1]
 * Output: 1
 *
 *  Example 2:
 * Input: nums = [4,1,2,1,2]
 * Output: 4
 *
 *  Example 3:
 * Input: nums = [1]
 * Output: 1
 */
public class E136SingleNumber {
    public static void main(String[] args) {
        int[] nums = {1,2,1,2,5};
        System.out.println(singleNumber(nums));

        System.out.println(singleNumber1(nums));

    }

    public static int singleNumber(int[] nums) {
        Map<Integer, Integer> tempMap = new HashMap<>();
        for (int num : nums) {
            if (tempMap.containsKey(num)) {
                int count = tempMap.get(num) + 1;
                tempMap.put(num, count);
            } else {
                tempMap.put(num, 1);
            }
        }
        for (Map.Entry<Integer, Integer> entry : tempMap.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }

        return -1;
    }

    /**
    如何才能做到线性时间复杂度和常数空间复杂度呢？

    答案是使用位运算。对于这道题，可使用异或运算 ⊕。异或运算有以下三个性质。

    1. 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
    2. 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
    3. 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

     假设数组中有 2m+1 个数，其中有 m 个数各出现两次，一个数出现一次。
     令 a1、a2、…、am为出现两次的 m 个数，ap为出现一次的数。
     根据性质 3，数组中的全部元素的异或运算结果总是可以写成如下形式：

     (a1⊕a1)⊕(a2⊕a2)⊕⋯⊕(am⊕am)⊕ap
     根据性质 2 和性质 1，上式可化简和计算得到如下结果：

     0⊕0⊕⋯⊕0⊕ap=ap
     因此，数组中的全部元素的异或运算结果即为数组中只出现一次的数字。

     **/


    public static int singleNumber1(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }



}
